A digital data processing system includes three basic elements, namely, a processor, a memory and an input/output system.
The memory stores information in addressable storage locations. This information includes data and instructions for processing the data. The processor fetches information from the memory, interprets the information as either an instruction or data, processes the data in accordance with the instructions, and returns the processed data to the memory for storage therein. The input/output system under control of the processor, also communicates with the memory element to transfer information, including instructions and data to be processed, to the memory, and to obtain processed data from the memory. Typically, the input/output system includes a number of diverse types of units, including video display terminals, printers, interfaces to the public telecommunications network, and secondary storage subsystems, including disk and tape storage devices.
Instructions processed by the processor are organized into one or more programs, each of which is executed in the context of a "process." A modern digital computer system typically can execute a plurality of processes concurrently. For example, a modern computer system may execute, in an interleaved fashion, a predetermined maximum number of processes each generally for selected amounts of time. At the end of a process's processing time, the computer system will stop processing that process and begin processing another process. A computer system may terminate processing of a particular process if the process, for example, requests an input/output operation, such as a transfer to or from a disk unit. Since, when a process requests such an input/output operation, the computer system typically waits until the completion of the input/output operation before it resumes processing the process that requested the input/output operation, and since an input/output operation typically can take a considerable amount of time, relative to the time required for the computer system to execute instructions, the computer switches to another process when a process that it is currently executing requests an input/output operation. While, with this "multi-programming" facility, the computer system may take longer to process each individual program, since the program's process is only executed during its assigned time slots, it will be appreciated that multi-programming does permit the computer system to process a plurality of programs in less total time, at least in part because the computer system is not stalled waiting for input/output operations to complete.
Multi-programming also provides other advantages, most notably that a number of processes may share and concurrently process, in a regulated manner, data stored in shared storage devices, such as, for example, disk storage units. To enhance the security of data, that is, to reduce the likelihood that data can be read or altered by unauthorized processes, computer systems often provide extensive security facilities for regulating access to particular data files by the various processes.
However, security of data in digital computer systems may be threatened by covert transmission of data between cooperating processes. For example, a process which has access to high-secrecy data may transmit the data to a process which is not authorized to read the disk files which contain the data. This may be accomplished by a "Trojan horse" in the process having access to the high-secrecy data (the "high-secrecy process") controlling various resources in the computer system which it shares with the other process, identified as the "spy process." The "Trojan horse" is a clandestine program in the high-secrecy process which may be unknown to the user of other programs in the high-secrecy process, and both it and the spy process can manipulate and observe the conditions of the shared resources. The shared resources thereby provide "channels" which can be used by the Trojan horse and the spy process to facilitate the convert transmission of high-secrecy information to the other process which would otherwise not have access to it.
Two general types of convert channels have been identified in computer systems, namely, timing channels and storage channels. Timing channels may arise as a result of the availability or unavailability of particular system resources during particular time intervals. For example, some types of instructions cause the processor to test system resources, such as interlocks, to determine whether they are set or cleared. Some such instructions may, for example, enable the processor to test the condition of an interlock to determine whether it is set, and, if not, set the interlock and perform some other operation. On the other hand, if, upon testing the condition of the interlock, the processor determines that the interlock is set, the processor stalls until the interlock is later cleared. Others of such instructions enable the processor to clear the interlock. Thus, if a program in one process issues an instruction that enables the processor to set an interlock, while the interlock is set, the processor stalls if another program attempts to execute a similar instruction until the interlock is cleared by the program in the first process. A Trojan horse in one process may transmit data by varying the rate at which it enables the processor to set the interlocks, and the spy process may determine the values of the data by determining the rates, at various times, at which it can concurrently enable the processor to execute instructions which would also set the interlock.
Storage channels also arise in response to control of shared resources, some of which may relate to various elements of a secondary storage subsystem. The storage channels may arise in a number of ways. Some storage channels may arise from various techniques which have been adopted to optimize use of, for example, a secondary storage subsystem in which data is stored in a movable-head disk storage device. A number of optimization techniques may be used in, for example, disk secondary storage subsystems to maximize the rate in which data may be stored in, or retrieved from a disk subsystem. For example, typically requests from a host to a disk subsystem to read data from, or write data to, various tracks on a disk are issued for tracks at random. If the disk subsystem were to process the requests in the order in which they were issued, the disk arm would be moving the disk head randomly over the tracks of the disk.
In one well-known optimization technique, known as the "elevator" technique, rather than moving the disk head randomly over the disk, the disk arm is controlled to sweep the head in alternate directions over the disk, that is, first from the rim toward the center, and, when it reaches the center, from the center toward the rim. As the arm moves the head over the disk, for example, track by track from the rim toward the center, the disk subsystem may store data on or read data from the successive tracks as it comes to them, and similarly as the arm moves the head from the center toward the rim, effectively processing the requests out of order. While the disk subsystem using the elevator technique may take longer to process a particular request, it processes large numbers of requests in less time since generally less total arm movement is required to process the requests.
However, since the elevator technique results in non-random movement of a disk head, a Trojan horse in one process can, by issuing requests to the disk subsystem, influence the direction of arm movement, which can be observed by the spy process. For example, suppose a spy process initially enables the disk arm to move the head to track 55, and stalls the processor until it receives notification that the disk head has reached track 55. Suppose further that the Trojan horse issues a request to enable the disk arm to move the head to one of two tracks on either side of track 55, with the direction identifying a particular data value (more specifically, suppose that the Trojan horse issues a request to enable the disk arm to move the disk head to track 53 to indicate a data value of zero, or to track 57 to indicate a data value of one) and immediately enables the processor to begin processing another process, in particular the spy process.
The spy process may determine the direction of arm movement enabled by the Trojan horse by issuing two requests which enable the disk arm to move the disk head to, for example, track 52 and track 58. Since the disk subsystem is implementing the elevator technique, if the Trojan horse had enabled the disk arm to move the head to track 53, since the direction of arm movement is toward lower-numbered tracks, the disk subsystem would complete the spy process's request to enable the disk arm to move the disk head to track 52, before it completed its request to enable the disk arm to move the disk head to track 58. Thus, when the spy process is notified of the completion of the request to move the head to track 52, it will determine that the Trojan horse had transmitted a data value of zero. However, if the Trojan horse had enabled the disk arm to move the disk head to, for example, track 57, since the direction of arm movement is toward higher-numbered tracks, the disk subsystem would first complete the spy process's request to enable the disk arm to move the disk head to track 58, so that, when the spy process is notified of the completion of that request, it will determine that the Trojan horse had transmitted a data value of one.
The use of the direction of movement of the disk arm as a covert channel can be eliminated by not using optimization techniques such as the elevator algorithm, as was suggested in M. Schaefer, et al., "Program Confinement In KVM/370", Proceedings of the 1977 ACM Annual Conference, 16-19 October 1977, Seattle, Wash., pp. 404-410. However, in some cases optimization techniques are architecturally specified in disk subsystems and cannot be eliminated, and in other cases the optimization techniques provide such significant improvements in disk performance that it is undesirable to eliminate them.